//代码主要结构源自懒猫老师
#include <iostream>
#include <queue>
#include <stack>
using namespace std;

const int MAX_VERTEX = 30;    // 图的最大顶点数

struct ArcNode  /* 边表 */
{
    int weight;     // 增加权值分量，代表活动时间=====
    int adjvex;
    ArcNode *next;
};

struct VertexNode  /* 顶点表 */
{
    int in;                // 增加入度字段-----
    char vertex;
    ArcNode *firstEdge;
};

class ALGraph {
private:
    VertexNode *adjList;  // 邻接表
    int vertexNum, arcNum;
    int *ve, *vl; // ve数组是事件最早发生时间，vl事件最迟发生时间(数组长度跟顶点数相等)=====
public:
    ALGraph(char v[], int n, int e);
    ~ALGraph();
    void inputEdges();
    bool setEdge(int vi, int vj, int weight);
    void displayData();

    bool TopologicalSort(int result[], int &count); // 拓扑排序
    bool CriticalPath();   // 求关键路径
};

ALGraph::ALGraph(char v[], int n, int e) {
    vertexNum = n;
    arcNum = e;
    adjList = new VertexNode[vertexNum];
    for (int i = 0; i < vertexNum; i++) {
        // 输入顶点信息，初始化顶点表
        adjList[i].in = 0;    // 增加in的初始化-----
        adjList[i].vertex = v[i];
        adjList[i].firstEdge = NULL;
    }
    ve = new int[vertexNum];
    vl = new int[vertexNum];
}

ALGraph::~ALGraph() {
    ArcNode *p, *pre;
    // 遍历顶点表数组，把顶点表指向的所有边结点删除
    for (int i = 0; i < vertexNum; i++) {
        p = adjList[i].firstEdge;
        adjList[i].firstEdge = NULL;
        while (p) {
            pre = p;
            p = p->next;
            delete pre;
        }
    }
    delete[] adjList;
    delete[] ve;
    delete[] vl;
}

void ALGraph::inputEdges() {  //=====
    cout << "请输入两个事件顶点编号(范围0-" << vertexNum - 1 << ")和活动时间:" << endl;
    for (int i = 0; i < arcNum; i++) {
        // 输入边的信息存储在边表中
        int vi, vj, weight;
        cin >> vi >> vj >> weight;   // 输入边依附的两个顶点的编号
        if (!setEdge(vi, vj, weight)) {
            cout << "输入的顶点编号超过范围或者相等，需要重新输入" << endl;
            i--;
        }
    }
}

bool ALGraph::setEdge(int vi, int vj, int weight) {  //=====
    // 修改setEdge函数，把vj顶点表中的入度+1 -----
    ArcNode *s;
    if (vi >= 0 && vi < vertexNum && vj >= 0 && vj < vertexNum && vi != vj) {
        // 创建一个边结点vj
        s = new ArcNode;
        s->adjvex = vj;
        s->weight = weight; //=====
        // 把边结点vj插入到顶点表vi项的邻接表中，成为第一个结点
        s->next = adjList[vi].firstEdge;
        adjList[vi].firstEdge = s;
        // vj顶点表中的入度+1   -----
        adjList[vj].in++;
        return true;
    } else {
        return false;
    }
}

void ALGraph::displayData() {
    ArcNode *p;
    cout << "输出图的存储情况：" << endl;
    for (int i = 0; i < vertexNum; i++) {
        cout << "顶点" << adjList[i].vertex << "的入度为：" << adjList[i].in << "，从这个顶点发出的的边为：" << endl; //-----
        p = adjList[i].firstEdge;
        if (!p)
            cout << "没有。" << endl;
        while (p) {
            cout << "<" << i << "," << p->adjvex << ">" << p->weight << endl;
            p = p->next;
        }
    }
}

bool ALGraph::TopologicalSort(int result[], int &count) {
    queue<int> Q; // 用队列存储入度为0的顶点
    for (int i = 0; i < vertexNum; i++) {
        ve[i] = 0; // 初始化事件最早发生时间
        if (adjList[i].in == 0) {
            Q.push(i); // 入度为0的顶点入队
        }
    }

    count = 0; // 初始化已处理的顶点数
    while (!Q.empty()) {
        int inVex = Q.front(); // 取出队头元素
        Q.pop();
        result[count++] = inVex; // 将当前顶点加入拓扑排序结果
        ArcNode *p = adjList[inVex].firstEdge;
        while (p) {
            int outVex = p->adjvex;
            if (--adjList[outVex].in == 0) { // 减少邻接点的入度，若为0则入队
                Q.push(outVex);
            }
            if (ve[inVex] + p->weight > ve[outVex]) { // 更新事件最早发生时间
                ve[outVex] = ve[inVex] + p->weight;
            }
            p = p->next;
        }
    }

    return count == vertexNum; // 若所有顶点都被处理，则返回true
}

bool ALGraph::CriticalPath() {
    int resultStack[MAX_VERTEX]; // 存储拓扑排序结果序列(存储下标)
    int resultTop;               // 拓扑排序有效顶点个数(栈顶指针)
    if (!TopologicalSort(resultStack, resultTop)) {
        return false; // 若图中有环，则无法求关键路径
    }

    // 初始化事件最迟发生时间vl
    for (int i = 0; i < vertexNum; i++) {
        vl[i] = ve[vertexNum - 1]; // 假设最后一个事件的最迟发生时间等于最早发生时间
    }

    // 逆拓扑排序计算vl数组
    for (int i = resultTop - 1; i >= 0; i--) {
        int inVex = resultStack[i];
        ArcNode *p = adjList[inVex].firstEdge;
        while (p) {
            int outVex = p->adjvex;
            if (vl[outVex] - p->weight < vl[inVex]) { // 更新事件最迟发生时间
                vl[inVex] = vl[outVex] - p->weight;
            }
            p = p->next;
        }
    }

    // 输出拓扑排序的顶点处理顺序
    cout << "拓扑排序的顶点处理顺序为：";
    for (int i = 0; i < resultTop; i++) {
        cout << resultStack[i] << " ";
    }
    cout << endl;

    // 输出ve数组的值
    cout << "事件最早发生时间ve数组：";
    for (int i = 0; i < vertexNum; i++) {
        cout << ve[i] << " ";
    }
    cout << endl;

    // 输出vl数组的值
    cout << "事件最迟发生时间vl数组：";
    for (int i = 0; i < vertexNum; i++) {
        cout << vl[i] << " ";
    }
    cout << endl;

    // 输出关键路径
    cout << "关键路径为：" << endl;
    for (int i = 0; i < vertexNum; i++) {
        ArcNode *p = adjList[i].firstEdge;
        while (p) {
            int outVex = p->adjvex;
            if (ve[i] == vl[outVex] - p->weight) { // 判断是否为关键活动
                cout << "<" << i << "," << outVex << ">" << p->weight << endl;
            }
            p = p->next;
        }
    }

    return true;
}

int main() {
    system("chcp 65001"); // 中文编码设置
    char vertex[MAX_VERTEX];
    int num, edge;

    cout << "请输入顶点个数和边的个数：";
    cin >> num >> edge;
    for (int i = 0; i < num; i++)
        vertex[i] = i + '0';

    ALGraph graph(vertex, num, edge);
    graph.inputEdges();
    graph.displayData();

    if (!graph.CriticalPath()) {
        cout << "这个图有回路，不能求关键路径。";
    }

    return 0;
}